﻿// 0813train03.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <limits>
#include <map>
#include <set>

using namespace std;


/*
 有一个大小是N * M的战场地图，
 被墙壁’#’ 分隔成大小不同的区域，上下左右四个方向相邻的空地 ‘.’，属于同一个区域，
 只有空地上可能存在敌人’E’，请求出地图上总共有多少区域里的敌人数小于K。

输入描述
第一行输入为N M K
N表示地图的行数，M表示地图的列数，K表示目标敌人数量 
N, M <= 100 
之后为一个N x M大小的字符数组

输出描述
敌人数小于K的区域数量

输入
3 5 2
..#EE
E.#E.
###..
输出1
 */

class Solution01
{
public:
    int result = 0;
    int curr_target_count = 0;
    void bfs(vector<vector<string>>& grid,
        vector<vector<bool>>&checked, 
        queue<pair<int, int>>&bfs_queue
    )
    {
        while (!bfs_queue.empty())
        {
            pair<int, int>node = bfs_queue.front();
            bfs_queue.pop();
            string node_val = grid[node.first][node.second];

            //满足要求，target+1
            if (node_val =="E")
            {
                curr_target_count += 1;
            }

            //遍历方向矩阵
            for (auto&dir_vec:DirectionGrid)
            {
                int curr_r = node.first + dir_vec[0];
                int curr_c = node.second + dir_vec[1];

                //未越界，未访问，可到达
                bool is_curr_r = curr_r >= 0 && curr_r < row_size;
                bool is_curr_c = curr_c >= 0 && curr_c < col_size;

                if (is_curr_r&&is_curr_c)
                {
                    bool is_visited = checked[curr_r][curr_c];
                    bool is_available = grid[curr_r][curr_c] != "#";

                    if (!is_visited&&is_available)
                    {
                        bfs_queue.push(make_pair(curr_r, curr_c));
                        //标记已访问
                        checked[curr_r][curr_c] = true;
                    }

                }

            }


            //while (!bfs_queue.empty())
        }

    }
    void solve01(vector<vector<string>>&grid, int limit)
    {
        //#不能通过
        //bfs_queue checked DirectionGrid
        row_size = grid.size();
        col_size = grid[0].size();

        //checked
        vector<bool>checked_status(col_size, false);
        vector<vector<bool>>checked(row_size, checked_status);

        //queue
        queue<pair<int, int>>bfs_queue;

        //双重循环
        for (int r=0; r<row_size; r++)
        {
            for (int c=0; c<col_size; c++)
            {
                //不为# 未访问
                string first_val = grid[r][c];
                bool is_first_visited = checked[r][c];
                bool is_first_available = first_val != "#";

                if (!is_first_visited && is_first_available)
                {
                    bfs_queue.push(make_pair(r, c));
                    //标记已访问
                    checked[r][c] = true;
                    //重置curr_target_count
                    curr_target_count = 0;
                    bfs(grid, checked, bfs_queue);
                    //敌人数小于K
                    if (curr_target_count<limit)
                    {
                        result += 1;
                    }

                }

                //for col_size
            }
            //for row_size
        }
        cout << result;

    }
private:
    int row_size = 0;
    int col_size = 0;
    vector<vector<int>>DirectionGrid = { {-1,0},{1,0},{0,-1},{0,1} };
};

/*
 给定两个字符串 s1 和 s2 和正整数 k，
 其中 s1 长度为 n1，s2 长度为 n2。

在 s2 中选一个子串，若满足下面条件，则称 s2 以长度 k 冗余覆盖 s1
该子串长度为 n1 + k
该子串中包含 s1 中全部字母
该子串每个字母出现次数不小于 s1 中对应的字母
给定 s1，s2，k，求最左侧的 s2 以长度 k 冗余覆盖 s1 的子串的首个元素的下标，如果没有返回-1。

举例：
s1 = “ab”
s2 = “aabcd”
k = 1
则子串 “aab” 和 “abc” 均满足此条件，由于 “aab” 在 “abc” 的左侧，“aab” 的第一个元素下标为 0，因此输出 0

输入描述
输入三行，第一行为 s1，第二行为 s2，第三行为 k
s1 和 s2 只包含小写字母

输出描述
最左侧的 s2 以长度 k 冗余覆盖 s1 的子串首个元素下标，如果没有返回 -1。

输入
ab
aabcd
1

输出
0

 */

class Solution02
{
public:
    bool checked(unordered_map<char, int>&sub_map, string&sub_cover)
    {
        unordered_map<char, int>cover_map;
        for (auto&oh_char:sub_cover)
        {
            cover_map[oh_char] += 1;
        }

        bool result = true;

        for (auto&map_item: sub_map)
        {
            char need_char = map_item.first;
            int need_count = map_item.second;

            if (cover_map[need_char]<need_count)
            {
                result = false;
                break;
            }
        }
        return result;
    }

    void solve02(string& sub_str, string& cover_str, int length)
    {
        if (cover_str.size()<sub_str.size() + length)
        {
            cout << -1;
            return;
        }

        unordered_map<char, int>sub_map;
        for (auto&oh_char:sub_str)
        {
            sub_map[oh_char] += 1;
        }

        int sub_length = sub_str.size() + length;
        //固定窗口大小
        
    	//
        int cover_size = cover_str.size();

        int result = -1;
        for (int left=0, right= sub_length-1; right<cover_size; left++,right++)
        {
            string cover_sub = cover_str.substr(left, sub_length);
            bool is_target = checked(sub_map, cover_sub);

            if (is_target)
            {
                result = left;
                break;
            }

        }
        cout << result;
        //solve02
    }
};


class Solution21
{
public:
    bool checked(unordered_map<char, int>& sub_map, string& sub_cover)
    {
        unordered_map<char, int>cover_map;
        for (auto& oh_char : sub_cover)
        {
            cover_map[oh_char] += 1;
        }

        bool result = true;

        for (auto& map_item : sub_map)
        {
            char need_char = map_item.first;
            int need_count = map_item.second;

            if (cover_map[need_char] < need_count)
            {
                result = false;
                break;
            }
        }
        return result;
    }

    void solve02(string& sub_str, string& cover_str, int length)
    {
        if (cover_str.size() < sub_str.size() + length)
        {
            cout << -1;
            return;
        }

        unordered_map<char, int>sub_map;
        for (auto& oh_char : sub_str)
        {
            sub_map[oh_char] += 1;
        }

        int sub_length = sub_str.size() + length;
        //固定窗口大小
        int left = 0, right = sub_length - 1;
        string cover_sub = cover_str.substr(left, sub_length);
        bool is_target = checked(sub_map, cover_sub);

        if (is_target)
        {
            cout << left;
            return;
        }

        //
        int cover_size = cover_str.size();

        int result = -1;
        for (int left = 1, right = sub_length; right < cover_size; left++, right++)
        {
            string cover_sub = cover_str.substr(left, sub_length);
            bool is_target = checked(sub_map, cover_sub);

            if (is_target)
            {
                result = left;
                break;
            }

        }
        cout << result;
        //solve02
    }
};


/*
给定M (0<M<=30)个字符(a-z)，从中取出任意字符(每个字符只能用一次)拼接成长度为N (0<N<=5)的字符串，
要求相同的字符不能相邻，
计算出给定的字符列表能拼接出多少种满足条件的字符串，
输入非法或者无法拼接出满足条件的字符串则返回0

输入描述
给定的字符列表和结果字符串长度，中间使用空格(" ")拼接

输出描述
满足条件的字符串个数

输入
aabc 3
输出
8

给定的字符为aabc，结果字符串长度为3，可以拼接成abc,acb,bac,bca,cba,cab,aba,aca，共8种

输入
abc 1
输出
3

给定的字符为abc，结果字符串长度为1，可以拼接成a,b,c，共3种
 */

class Solution03
{
public:
    vector<vector<char>>result_vec;
    vector<char>track_vec;
    void backTrack(vector<char>& str_vec, vector<bool>&used)
    {
        if (track_vec.size()==target_size)
        {
            result_vec.push_back(track_vec);
            return;
        }

        for (int i=0; i<str_vec.size();i++)
        {
            if (used[i]) continue;
            if (i > 0 && str_vec[i] == str_vec[i - 1]&&!used[i-1]) continue;
            if (str_vec[i] == track_vec.back()) continue;

            track_vec.push_back(str_vec[i]);
            used[i] = true;
            backTrack(str_vec, used);
            track_vec.pop_back();
            used[i] = false;
        }

    }

    void solve03(vector<char>&str_vec, int sub_size)
    {
        if (sub_size>str_vec.size())
        {
            cout << 0;
            return;
        }

        target_size = sub_size;
        //排序,方便剪枝
        sort(str_vec.begin(), str_vec.end());

        int vec_size = str_vec.size();
        vector<bool>used(vec_size, false);

        for (int i=0;i<vec_size; i++)
        {
            if (used[i]) continue;
            if (i > 0 && str_vec[i] == str_vec[i - 1]) continue;
            track_vec.push_back(str_vec[i]);
            used[i] = true;
            backTrack(str_vec, used);
            used[i] = false;
            track_vec.pop_back();
        }

        //for (auto&min_vec:result_vec)
        //{
        //    string str;
        //    for (auto&oh_char:min_vec)
        //    {
        //        str += oh_char;
        //    }
        //    cout << str << endl;
        //}
        cout << result_vec.size();
    }
private:
    int target_size = 0;
};


int main()
{
	//{
 //       //aabc 3
 //       string str = "abca";
 //       int sub_size = 3;
 //       //string str;
 //       //cin >> str;
 //       //int sub_size;
 //       //cin >> sub_size;
 //       vector<char>char_vec;
 //       for (auto&oh_char:str)
 //       {
 //           char_vec.push_back(oh_char);
 //       }
 //       Solution03 solu;
 //       solu.solve03(char_vec,sub_size);

 //       return 0;
	//}
	{
/*
ab
aabcd
1

abc
dfs
10
*/
        //string sub_str, cover_str;
        //cin >> sub_str >> cover_str;
        string sub_str = "abc", cover_str = "abcabc";
        int length = 3;
        //int length;
        //cin >> length;

        Solution02 solu;
        solu.solve02(sub_str, cover_str, length);

        return 0;
	}
/*
3 5 2
..#EE
E.#E.
###..
*/
    int row_size, col_size, limit;
    cin >> row_size >> col_size >> limit;

    cin.ignore();

    vector<string>str_vec;
    for (int i=0; i<row_size; i++)
    {
        string input;
        getline(cin, input);
        str_vec.push_back(input);
    }
    //int limit = 2;
    //string str1 = "..#EE";
    //string str2 = "E.#E.";
    //string str3 = "###..";
    //vector<string>str_vec = { str1,str2,str3 };

    vector<vector<string>>grid;
    for (auto&oh_str:str_vec)
    {
        vector<string>mini_vec(col_size);
        for (int c=0;c<col_size;c++)
        {
            char oh_char = oh_str[c];
            string curr;
            curr += oh_char;
            mini_vec[c] = curr;
        }
        grid.push_back(mini_vec);
    }
    Solution01 solu;
    solu.solve01(grid, limit);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
